%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A directed or undirected graph $G = (V, E)$ of order $n > 0$. A
  vertex $s$ from which to start the search. The vertices are numbered
  from $1$ to  $n = |V|$, i.e.~$V = \{1, 2, \dots, n\}$.
\Ensure A list $D$ of distances of all vertices from $s$. A tree $T$
  rooted at $s$.
%%
%% algorithm body
\State $S \gets [s]$\Comment{stack of nodes to visit}
\State $D \gets [\infty, \infty, \dots, \infty]$\Comment{$n$ copies of $\infty$}
\State $D[s] \gets 0$
\State $T \gets [\,]$
\While{$\length(S) > 0$\label{alg:DFS:while_loop_tests_non_empty_stack}}
  \State $v \gets \pop(S)$
  \For{\rm each $w \in \adj(v)$\label{alg:DFS:for_loop_visit_neighbors}}
    \If{$D[w] = \infty$\label{alg:DFS:if_test_unvisited_neighbors}}
      \State $D[w] \gets D[v] + 1$
      \State $\push(S, w)$
      \State $\append(T, vw)$
    \EndIf
  \EndFor
\EndWhile
\State \Return $(D, T)$
\end{algorithmic}
